/**
 * 
 */
package tree.passed2;

import java.util.LinkedList;
import java.util.Queue;

import tree.Node;
import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 *
 */
public class BinaryHeightAndWidth {
	public static int heightRecursive(Node<Integer> root) {
		if (root == null)
			return 0;
		return 1 + Math.max(heightRecursive(root.left),
		        heightRecursive(root.right));
	}

	public static int heightIterative(Node<Integer> root) {
		if (root == null)
			return 0;
		int height = 1;
		int levelSize = 1;
		Queue<Node<Integer>> queue = new LinkedList<Node<Integer>>();
		queue.add(root);
		while (!queue.isEmpty()) {
			Node<Integer> node = queue.poll();
			levelSize--;
			if (node.left != null)
				queue.add(node.left);
			if (node.right != null)
				queue.add(node.right);

			if (levelSize == 0) {
				levelSize = queue.size();
				if (levelSize != 0)
					height++;
			}

		}

		return height;
	}

	public static int widthIterative(Node<Integer> root) {
		if (root == null)
			return 0;
		Queue<Node<Integer>> queue = new LinkedList<Node<Integer>>();
		int currLevel = 1;
		int nextLevel = 0;
		int maxWidth = 1;
		queue.add(root);
		while (!queue.isEmpty()) {
			Node<Integer> node = queue.poll();
			if (node.left != null) {
				queue.add(node.left);
				++nextLevel;
			}
			if (node.right != null) {
				queue.add(node.right);
				++nextLevel;
			}
			if (--currLevel == 0) {
				maxWidth = nextLevel > maxWidth ? nextLevel : maxWidth;
				currLevel = nextLevel;
				nextLevel = 0;
			}
		}

		return maxWidth;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	Maximum Depth of Binary Tree
	Given a binary tree, find its maximum depth.

	The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.	
	 */
	public int maxDepthR(TreeNode root) {
		if (root == null)
			return 0;

		return Math.max(maxDepthR(root.left), maxDepthR(root.right)) + 1;
	}

	/**
	Minimum Depth of Binary Tree
	Given a binary tree, find its minimum depth.

	The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
	 */
	public int minDepthRa(TreeNode root) {
		if (root == null)
			return 0;
		int left = minDepthRa(root.left);
		int right = minDepthRa(root.right);
		return left == 0 || right == 0 ? right + left + 1 : Math.min(left, right) + 1;
	}
	
	public int minDepthRb(TreeNode root) {
		if (root == null)
			return 0;

		if (root.left == null && root.right == null)
			return 1;
		if (root.left == null)
			return minDepthRb(root.right) + 1;
		if (root.right == null)
			return minDepthRb(root.left) + 1;

		return Math.min(minDepthRb(root.left), minDepthRb(root.right)) + 1;
	}
	
	public int minDepth(TreeNode root) {
		if (root == null)
			return 0;

		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		queue.offer(null);
		int level = 1;
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node == null) {
				level++;
				if (!queue.isEmpty())
					queue.offer(null);
			} else {
				if (node.left == null && node.right == null) {
					return level;
				}
				if (node.left != null)
					queue.offer(node.left);
				if (node.right != null)
					queue.offer(node.right);
			}
		}

		return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> root = CreateUtils.bstWithTenNodes();
		PrintUtils.printBinaryTree(root);
		System.out.println("height: " + heightIterative(root));
		System.out.println("width: " + widthIterative(root));
	}

	/**
	 * 
	 */
	public BinaryHeightAndWidth() {
		// TODO Auto-generated constructor stub
	}
}
